Linked List

A linked list is a linear data structure where elements (called nodes) are connected using pointers (or references). Unlike arrays, linked lists don’t store elements in contiguous memory. Instead, each node contains:

1. Data → The actual value.
2. Pointer (next) → A reference to the next node in the sequence.

Think of it like a chain of boxes:

• Each box has data + an arrow pointing to the next box.
• The last box points to NULL, meaning end of the list.

Why Use Linked List Instead of Array?

• Dynamic size → No need to declare fixed size like arrays.
• Efficient insertion/deletion → Adding/removing elements doesn’t require shifting.
• Memory utilization → Uses memory as needed (non-contiguous).

But:

• Slower access → Unlike arrays, you can’t access by index directly. You must traverse from the head.
• Extra memory → Each node needs extra space for a pointer.

Types of Linked Lists

• Singly Linked List → Each node points to the next node. (One direction only)
• Doubly Linked List → Each node has two pointers: next (to next node) and prev (to previous node). (Two directions)
• Circular Linked List → Last node points back to the head, forming a loop.

Structure of a Node

C Programming

struct Node {
    int data;          // Value
    struct Node* next; // Pointer to next node
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

C++ Programming

class Node {
public:
    int data;
    Node* next;

    Node(int value) {
        data = value;
        next = nullptr;
    }
};

class LinkedList {
private:
    Node* head;

public:
    LinkedList() {
        head = nullptr;
    }

    // Insert at end
    void insertEnd(int value) {}
}

int main() {
    LinkedList ll;

    ll.insertEnd(10);
    ll.insertEnd(20);
    ll.insertEnd(30);
}

Floyd's Cycle Finding Algorithm

• It also called tortoise algorithm
• Use two pointer to move through the sequence at different speed

slow pointer => move one step ahead
fast pointer => move two step ahead

How It Works

When slow pointer enter the loop, fast pointer must be inside loop

If we consider distance between slow and fast pointer. At begining, it will be 0, then 1, then 2 and eventually it well become n but the distance between fast and slow(reverse) gradually reduce and eventually they see each other and loop detected.

Loop

A loop means the last node of the linked list connected back to a node in the same linke list.

       Loop                     Not Loop
------------------------------------------------
1 → 2 → 3 → 4 → 5      1 → 2 → 3 → 4 → 5 → 6 → 7
          ↑     │                ↑     │
          └─────┘                └─────┘

Start Point

• Distance covered by slow pointer: m + n*x + k
• Distance covered by fast pointer: m + n*y + k
  • m: straight distance
  • n: length of the loop
  • x, y: number of time loop iterate
  • k: distance between start point and collision point

Distance Calcualtion

fast        = 2 * slow
m + n*y + k = 2 * (m + n*x + k)
         ny = m + k + 2nx
     ny-2nx = m + k
    n(y-2x) = m + k
n(y-2x) - k = m
     ni - k = m

• y-2x times of extra iteration is used to detect the collison
• m is the distance of head to start which is ni-k or ni+k(reverse).
• So, to get start point, iterate the distance between head to start(m) evenutally equally with (ni + k)
  • That means we need to iterate the loop
  • As well as the linst from head.